Llenguatge formal

A matemàtiques, lògica, i ciències de la computació, un llenguatge formal és un llenguatge on els símbols primitius i regles per a unir aquests símbols estan formalment especificats.^[1] Al conjunt dels símbols primitius se l'anomena l'alfabet (o vocabulari) del llenguatge, i al conjunt de les regles se l'anomena la gramàtica formal (o sintaxi). A una cadena de símbols formada d'acord amb la gramàtica se l'anomena una fórmula ben formada (o paraula) del llenguatge. Estrictament parlant, un llenguatge formal és idèntic al conjunt de totes les seves fórmules ben formades.

Per exemple, un alfabet podria ser el conjunt {a, b}, i una gramàtica podria definir a les fórmules ben formades com aquelles que tenen el mateix nombre de símbols a que b. Llavors, algunes fórmules ben formades del llenguatge serien: ab, ba, abab, ababba, etc., I el llenguatge formal seria el conjunt de totes aquestes fórmules ben formades.

Per a alguns llenguatges formals hi ha una semàntica formal que pot interpretar i donar significat a les fórmules ben formades del llenguatge. Tanmateix, una semàntica formal no és condició necessària per definir un llenguatge formal, i això és una diferència essencial amb els llenguatges naturals.

En alguns llenguatges formals, la paraula buida (és a dir, la cadena de símbols de longitud zero) està permesa, notant-se freqüentment mitjançant ${\displaystyle \epsilon \,}$, ${\displaystyle i\,}$ o ${\displaystyle \lambda \,}$.